#ifndef _GRAFO
#define _GRAFO

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <iomanip>
#include <cstring>

#include "nodo.h"

class Grafo{

    private:

        //Nodos que conforman el grafo
        Nodo **nodos;
        
        //Tamaño del grafo
        int tam;
        
        //Color máximo asociado al grafo
        int colorMax;
        
        //Arreglo que guarda soluciones parciales encontradas
        int *solParcial;
        
        /*
         * Funcion que realiza una coloracion recursiva siguiendo el algoritmo
         * de Brown
         *
         * Entrada: Entero que indica el identificador del nodo a colorear
         *
         * Salida: -1 si el algoritmo ha finalizado, o el número del próximo nodo
         *         a recolorear
         */
        int auxiliarBrown(int n);        
        
        /*
         * Método que realiza la coloración recursiva siguiendo el algoritmo de
         * Brown-Korman
         *
         * Entrada: Entero que indica la posición del siguiente nodo a colorear
         *
         * Salida: -1 si el algoritmo ha finalizado, o el número del próximo nodo
         *         a recolorear
         */
        int auxiliarBrownKorman(int n);
        
        /*
         * Método que coloca en la posición indicada el nodo con menor cantidad 
         * de colores válidos posibles entre la posición y el resto de los nodos
         * sin colorear
         *
         * Entrada: Posición desde la cual se reordenará
         */
        void reordenar(int n);
         
        /*
         * Método que ordena los nodos del grafo en base a su grado, usando Merge Sort
         *
         * Entrada: Posiciones entre las que se deben ordenar los nodos
         */
        Nodo **ordenarNodos(int i, int f);
        
        /*
         * Método auxiliar al algoritmo de ordenarNodos()
         *
         * Entrada: - Apuntadores a los dos arreglos de nodos a mezclar, junto con sus tamanos
         * Salida: - Apuntador al arreglo con los elementos de ambos parámetros ordenados
         */
        Nodo **mezcla(Nodo **a, int tamA, Nodo **b, int tamB);

    public:

        Grafo(int t);

        int getTam();

        Nodo *getNodo(int i);

        void agregarArco(int f, int d);

        void sortAdyacentes();

        /*
         * Funcion que decolora todos los nodos del grafo
         */
        void inicializar();

        /*
         * Funcion que imprime el grafo
         */
        void imprimir();
        
        /*
         * Funcion que colorea la instancia del grafo usando el algoritmo
         * de Brown
         */
        void colorearBrown();     
        
        /*
         * Metodo que verifica que la coloracion actula del grafo es valida
         * 
         * Salida: boolean que indica si la coloracion es valida
         */
        bool tieneColoracionValida();
        
        /*
         * Metodo para obtener la coloracion maxima setteada del grafo
         *
         * Salida: Entero que contiene la coloracion maxima setteada por tieneColoracionValida
         */
        int getColorMax();
        
        /*
         * Método que colorea el grafo utilizando el algoritmo de Brown-Korman
         */
        void colorearBrownKorman();
        
};

#endif